package dataStructure.sort.mergeSort;

import dataStructure.sort.quickSort.QuickSort;

import java.util.Arrays;

/**
 * @author lhn
 * @date 2024-08-31 16:45
 */

public class MergeSort {
    static int count = 0;
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[arr.length];

        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));

        MergeSort.sort(arr, 0, arr.length - 1, temp);

        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;   //中间索引
            //向左递归分解
            sort(arr, left, mid, temp);
            //向右递归分解
            sort(arr, mid + 1, right, temp);
            //合并
            merger(arr, left, right, temp, mid);
        }
    }

    /**
     * 合并的方法
     * @param arr 需要排序的数组
     * @param left  左侧索引
     * @param right  右侧索引
     * @param temp  临时数组
     * @param mid  中间索引
    */
    public static void merger(int[] arr, int left, int right, int[] temp, int mid) {
        System.out.println("第" + (++count) + "次调用merger");
        int i = left; // 左序列指针
        int j = mid + 1; // 右序列指针
        int t = 0; //temp的指针

        //1.左右序列按顺序进行对比，把较小值放入temp中，直到一个序列中的值填充完毕
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t++;
                i++;
            } else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }

        //2.把剩余的序列值填充到temp中
        //2.1 左序列剩余值填充
        while (i <= mid) {
            temp[t] = arr[i];
            t++;
            i++;
        }

        //2.2 右序列剩余值填充
        while (j <= right) {
            temp[t] = arr[j];
            t++;
            j++;
        }

        //3.将temp中的值拷贝到arr中 ？
        t = 0;  // 初始化一个计数器，用于追踪temp数组中的当前位置
        int tempLeft = left;  // tempLeft用于在原数组arr中追踪当前正在填充的位置，起始于left（当前合并区间的左边界）

        // 循环直到tempLeft（当前正在arr中填充的位置）超过了right（当前合并区间的右边界）
        //第一次 0 1
        //第二次 2 3
        //第三次 0 3
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];  // 将temp数组中的当前元素（由t索引）复制到arr的当前位置（tempLeft）
            t++;  // 移动temp数组的索引，以便在下一次迭代中处理下一个元素
            tempLeft++;  // 移动arr的索引，以便在下一次迭代中填充下一个位置
        }

        System.out.println(Arrays.toString(arr));
    }
}
